The phenomena of signal echo occurs when a signal passes through an interface from a first transmission medium to a second transmission medium. An impedance mismatch across the interface will cause a portion of the energy of the signal to be :reflected back toward the source of the signal as an echo signal. The remaining portion of the energy of the signal propagates along the second medium.
In communication applications, it is desirable to eliminate the echo signal, for example, to improve the quality of audio signals or prevent the occurrence of errors in data transmission. Basic echo cancellation techniques are explained in: the Bell System Technical Journal, Vol. 59, No. 2, February 1980, pp. 149-159. One echo elimination technique discussed in the above journal is to detect when a signal is being transmitted in one direction and to attenuate all signals passing in the other direction. Errors in detecting the presence or absence of a signal can cause signal clipping when this echo elimination technique is used. Another technique utilizes subtractive attenuation. To eliminate the echo, the echo is replicated, such as being synthesized by an adaptive filter, then subtracted from the signal. Subtractive attenuation is more signal transparent and reduces signal clipping effects.
Another form of subtractive attenuation is achieved with an echo canceler having fixed coefficients designed to approximate the impulse response of the echo path. Since the impulse response of the echo path is not known, this technique results in imperfect echo canceling. More precise echo canceling is achieved when the echo canceler is adaptive. In an adaptive echo canceler, the tap weights of the echo canceler filter are changed over time to replicate the impulse response of the unknown echo path.
If a FIR filter structure is employed in an echo path, the filter would ideally require an infinite number of tap weights since the unknown echo path generally has an impulse response of infinite duration. An adaptive infinite impulse response filter having only a few tap weights could be used to achieve the necessary echo cancellation. Adaptive infinite impulse response filters, however, may become unstable. As a compromise, an adaptive FIR filter, having a finite number of tap weights, has been employed in echo cancellation applications. Adaptive FIR filters do not perfectly cancel the echo signal.
An adaptive echo canceler adapts to the impulse response of the echo path. When some of the elements of the echo path are known, the known elements can be individually optimized to shorten their impulse response length, that is, to reduce the number of tap weights. The reduced number of tap weights of individual elements contribute to shorten the length of the echo canceler. A reduced number of tap weights in a digital filter results in a reduced number of multiply and add functions to carry out the filtering. Some of the elements in the echo path are digital filters. Digital filters introduce a group delay distortion and a total delay. To optimize a filter, and thereby minimize its length, both the group delay distortion and the total delay must be minimized.
A constant group delay distortion can be achieved only by a linear phase filter. Small variations in group delay distortion can be compensated for in an adaptive equalizer. The group delay through a filter must be as small as possible in the pass band of the filter. Minimizing the group delay cannot be achieved in a linear phase filter. Since the impulse response of the echo path is generally infinite in duration, to perfectly cancel an echo signal requires an echo canceler that has an infinite impulse response. A minimum phase FIR filter provides both the shortest filter length and the minimum group delay distortion in a single filter. A minimum phase FIR filter also has all of its zeros on or inside the unit circle in the complex z-plane. Equivalently, a minimum phase FIR filter has no zeros outside the unit circle in the complex z-plane.
To employ a minimum phase FIR filter in an echo path would provide enhanced echo cancellation in that the length of the echo canceler would be shorter than for prior art methods. A further improvement in echo cancellation can be achieved by employing in an echo path a filter designed in accordance with the minimum phase alternation theorem set forth in Chen and Parks, "Design of Optimal Minimum Phase FIR Filters," Signal Processing, Vol. 10, Jun. 1986, pp. 369-383. A minimum phase FIR filter designed to meet the minimum phase alternation theorem will hereafter be referred to as an optimum minimum phase FIR filter. An optimum minimum phase FIR filter has the shortest filter length and minimum group delay for a given set of magnitude constraints on the ideal frequency response. Group delay distortion results from nonlinear phase. Although an optimum minimum phase FIR filter does not have perfectly linear phase, small deviations within the passband are permitted and are compensated for in an adaptive equalizer. However, extensive use of minimum phase FIR filters has been prevented by computational difficulties in precisely calculating the filter coefficients. Minimum phase FIR filters were a curiosity, interesting to theoreticians but of little practical application.
There are several reports in the literature of attempts to design minimum phase FIR filters. For example: Hermann and Schussler, "Design Of Non-recursive Digital Filters With Minimum Phase," Electronic Letters, 1970, Vol. 6, pp. 329-330; Kamp and Wellekens, "Optimal Design of Minimum Phase FIR Filters"; Chit and Mason, "Design of minimum phase FIR digital filters", IEE Proceedings, Vol. 135, December 1988, pp. 258-264; and Parks and Burrus, Digital Filter Design, John Wiley and Sons, New York, N.Y., 1987. However, the skilled artisan can not presently use these methods to design practical minimum phase FIR filters because of limitations that render the methods unable to accommodate more complex filter designs of practical importance or not consistently reliable.
Hermann and Schussler introduced a method for specifying a minimum phase FIR filter to convert a filter specification into a linear phase filter and subsequently the linear phase filter into a minimum phase FIR filter. The Hermann and Schussler method has at least two major shortcomings. Firstly, it is not sufficiently general; the method can be used to design two-band filters but cannot accommodate filters requiring more than one stop band. Secondly, infinite attenuation cannot be specified at specific frequencies. In other words, the exact location of a zero cannot be specified. Using the Hermann and Schussler method, the skilled artisan can specify only limited attenuation over a frequency band.
Kamp and Wellekens reported a method for optimal design of minimum phase FIR filters. A constrained approximation procedure was used to obtain the magnitude :function and the transmission zeros in the stopband(s). The zeros inside the unit circle are calculated via a low-degree polynomial factorization. A straightforward exchange algorithm is presented which achieves the constrained approximation step. This method has the same shortcomings as the Hermann and Schussler method.
Chit and Mason described a method for designing minimum phase FIR digital filters. The filter coefficients are determined through a least means squared (LMS) algorithm such that the realized filter coefficients are produced at the final convergence. The cost functions in the adaptation of the LMS algorithm are minimized. These cost functions are the frequency domain specifications of the desired filter. However, convergence noise in the LMS calculations causes nonoptimal location of filter zeros.
Parks and Burrus disclose a three step procedure, similar to Hermann and Schussler, for designing minimum phase FIR digital filters. The Parks and Burrus method takes advantage of characteristics of the impulse response polynomial to reduce the order of a polynomial ultimately factored. For each zero crossing on the frequency axis, a double pair of complex zeros (four zeros) is located on the unit circle at that frequency. The four zeros form a fourth order polynomial which can be readily factored out of the impulse response polynomial, or a reduced order polynomial from which other double pairs of complex zeros have been factored. Factoring the remaining reduced order polynomial is relatively easier than factoring the impulse response polynomial. The order of the remaining polynomial to be factored will always be less than the order of the original impulse response. Narrow passband filters have nearly all of their zeros on the unit circle. These zeros could be readily factored out of the impulse response polynomial. Factoring out these zeros significantly reduces the order of the impulse response polynomial.
Conversely, for narrow stopband filters, the impulse response is a very high order polynomial and few zeros are located on the unit circle. The Parks and Burrus method does not provide a significant reduction in the order of the polynomial to be factored. Even when the zeros on the unit circle are factored out, the remaining polynomial is very close in order to the order of the impulse response polynomial, and the difficulty of factoring the very high order polynomial is not overcome.
It would be desirable to employ minimum phase FIR filters or optimum minimum phase FIR filters in an echo path to minimize the impulse response length and the group delay of the filter. A method for precisely calculating filter coefficients for a minimum phase FIR filter that overcomes the problems of the prior art would facilitate using such filters. Employing minimum phase FIR filters, or optimum minimum phase FIR filters, in an echo path contributes to minimizing the length of an echo canceler. The method would be sufficiently general to accommodate multiple stop bands and permit precise location of zeros.